/*
 * @Author: szx
 * @Date: 2022-01-11 13:33:31
 * @LastEditTime: 2022-01-11 13:43:05
 * @Description:
 * @FilePath: \leetcode\500-599\509\509.js
 */
/**
 * @param {number} n
 * @return {number}
 */
// var fib = function (n) {
//     if (n == 0) return 0;
//     else if (n == 1) return 1;
//     return fib(n - 1) + fib(n - 2);
// };

// var fib = function (n) {
//     if (n <= 1) return n;
//     const dp = new Array(n);
//     dp[0] = 0;
//     dp[1] = 1;
//     for (let i = 2; i <= n; i++) {
//         dp[i] = dp[i - 1] + dp[i - 2];
//     }
//     return dp[n];
// };
var fib = function (n) {
    if (n <= 1) return n;
    let dp0 = 0,
        dp1 = 1,
        res = 1;
    for (let i = 2; i <= n; i++) {
        res = dp0 + dp1;
        dp0 = dp1;
        dp1 = res;
    }
    return res;
};
console.log(fib(4));
